//
// Created by 86152 on 2021/7/25.
//

#ifndef DATASTRUCTURE_TREE_H
#define DATASTRUCTURE_TREE_H

#include <iostream>
#include <stack>
namespace Tree {


// 节点
    class Node {
    private:
        int data;

    public:
        Node *left;
        Node *right;
        int ltag;
        int rtag;

        Node(int data) : data(data) {
            ltag = 0;
            rtag = 0;
            left = nullptr;
            right = nullptr;
        }

        void setData(int data) {
            Node::data = data;
        }

        int getData() const {
            return data;
        }
    };

// 先序线索化二叉树

    void InThread(Node *root, Node *&pre) {
        if (root == nullptr)return;

        if (root->left == nullptr) {
            root->ltag = 1;
            root->left = pre;
        }
        if (pre != nullptr && (pre)->rtag == 0) {
            (pre)->rtag = 1;
            (pre)->right = root;
        }
        pre = root;

        if (root->ltag == 0) {
            InThread(root->left, pre);
        }


        if (root->rtag == 0) {
            InThread(root->right, pre);
        }
    }

    void OrThread(Node *root, Node *&pre) {
        if (root == nullptr)return;

        if (root->ltag == 0) {
            OrThread(root->left, pre);
        }

        if (root->left == nullptr) {
            root->ltag = 1;
            root->left = pre;
        }
        if (pre != nullptr && (pre)->rtag == 0) {
            (pre)->rtag = 1;
            (pre)->right = root;
        }
        pre = root;

        if (root->rtag == 0) {
            OrThread(root->right, pre);
        }
    }

    void PostThread(Node *root, Node *&pre) {
        if (root == nullptr)return;

        if (root->ltag == 0) {
            PostThread(root->left, pre);
        }

        if (root->rtag == 0) {
            PostThread(root->right, pre);
        }

        if (root->left == nullptr) {
            root->ltag = 1;
            root->left = pre;
        }
        if (pre != nullptr && (pre)->rtag == 0) {
            (pre)->rtag = 1;
            (pre)->right = root;
        }

        pre = root;
    }


    // 中左右，第一个节点必然是中间节点
    Node* in_first(Node* root){
        return root;
    }
    // 中左右，rtag == 1，返回right  ltag == 0 代表存在左节点，应该返回， ltag == 1 代表没有左节点，应该返回右节点
    // 综上，rtag == 1 || rtag == 1 返回right  其他返回left
    Node* in_next(Node* root){
        if (root->ltag == 1 || root->rtag == 1) return root->right;
        return root->left;
    }
    // 中左右
    void InThread_visited(Node* root){
        for (Node* i = in_first(root); i != nullptr; i = in_next(i)){
            std::cout << i->getData() << " ";
        }
        std::cout << std::endl;
    }

    // 左中右，第一个节点应该是最左节点
    Node* or_first(Node* root){
        Node* r = root;
        while (r->ltag == 0) r = r->left; // 判断停止条件必须是ltag
        return r;
    }
    // 中左右， 如果 rtag == 1返回right， rtag == 0，表示有右节点，应该返回右节点的最左节点
    Node* or_next(Node* root){
        if (root->rtag == 0){
            return or_first(root->right);
        }
        return root->right;
    }
    // 左中右 第一个节点是最左下角，rtag == 0，
    void OrThread_visited(Node* root){
        for (Node* i = or_first(root); i != nullptr; i = or_next(i)){
            std::cout << i->getData() << " ";
        }
        std::cout << std::endl;
    }

    void pre(Node* root){
        std::stack<Node*> stack;
        while (root != nullptr  || !stack.empty()){
            if (root != nullptr){
                stack.push(root);
                std::cout << root->getData() << " ";
                root = root->left;
            }else{
                root = stack.top()->right;
                stack.pop();
            }
        }
        std::cout << std::endl;
    }

    void order(Node* root){
        std::stack<Node*> stack;
        while (root != nullptr  || !stack.empty()){
            if (root != nullptr){
                stack.push(root);
                root = root->left;
            }else{
                root = stack.top();
                std::cout << root->getData() << " ";
                root = root->right;
                stack.pop();
            }
        }
        std::cout << std::endl;
    }
    void Test_visited() {
#define ms 50
        int root[ms];
        for (int i = 0; i < ms; ++i) {
            root[i] = i;
        }
    }

    void Test_thread() {
        Node *root[7];
        for (int i = 0; i < 7; ++i) {
            root[i] = new Node(i + 1);
        }

        root[0]->left = root[1];
        root[0]->right = root[2];

        root[1]->left = root[3];
        root[1]->right = root[4];

        root[2]->left = root[5];
        root[2]->right = root[6];

        Node *p = nullptr;
//        pre(root[0]); // 先序遍历
//        InThread(root[0], p); // 先序线索化
//        InThread_visited(root[0]);  // 先序访问线索二叉树

        order(root[0]);
        OrThread(root[0], p);
        p->rtag = 1;
        p->right = nullptr;

        OrThread_visited(root[0]);




//        for (int j = 0; j < 7; ++j) {
//            printf("%08p  %08p  %d  %d  %08p  %8d\n", root[j], root[j]->left, root[j]->ltag, root[j]->rtag,
//                   root[j]->right, root[j]->getData());
//            delete root[j];
//        }
    }
}


#endif //DATASTRUCTURE_TREE_H
